// 按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树,例如输入：ABDH##I##EJ##K##CF#L##G##
// 求二叉树中最后一条最长的路径；

// 输入：ABDH##I##EJ##K##CF#L##G##

// 输出：二叉树中最后一条最长的路径:A C F L

#include <iostream>
#include <stack>
#include <cstdio>
#define MAXSIZE 1000
using namespace std;
#define MAX  200
typedef struct BiNode
{
	char data;
	struct BiNode *lchild;
	struct BiNode *rchild;
}BiNode,*BiTree;

BiTree creatbitree()//递归法先序建立二叉树
{
    BiTree T;
    char ch;
    //cin >> ch;
    scanf("%c", &ch);
    if(ch=='#')
        T = NULL;
    else
    {
        T = new BiNode;
        T->data = ch;
        T->lchild = creatbitree();
        T->rchild = creatbitree();
    }
    return T;
}

void longest_path(BiTree T,char *path,int &len,char *longestpath,int &longest_len)
{
    int j;
    if(T!=NULL)
	{
		if(T->lchild==NULL&&T->rchild==NULL)//当遇到叶子结点时，路径完毕 
		{
			path[len]=T->data;
			if(len>=longest_len)//如果长于最长路径的长度就替换 
			{
				for(j=0;j<=len;j++)
				{
					longestpath[j]=path[j];
				}
				longest_len=len;//最长路径长度更新
			}
		}
		else//当遇到的不是叶子结点时，该条路径继续 
		{
			path[len++]=T->data;
			longest_path(T->lchild ,path,len,longestpath,longest_len);
			longest_path(T->rchild ,path,len,longestpath,longest_len);
			len--;
		}
	}
}
int main()
{
	BiTree T;
	T=creatbitree();
	char path[MAX];
	char longestpath[MAX];
	int len=0;
	int longest_len=0;
	longest_path(T,path,len,longestpath,longest_len);
	cout<<"二叉树中最后一条最长的路径:"; 
	for(int i=0;i<=longest_len;i++)
	{
		cout<<longestpath[i]<<' ';
	}
	
}
